Search Results

Documents authored by Alt, Helmut

Found 2 Possible Name Variants:

Alt, Helmut

Document
DOI: 10.4230/LIPIcs.ISAAC.2017.4
Placing your Coins on a Shelf

Authors: Helmut Alt, Kevin Buchin, Steven Chaplick, Otfried Cheong, Philipp Kindermann, Christian Knauer, and Fabian Stehn

Published in: LIPIcs, Volume 92, 28th International Symposium on Algorithms and Computation (ISAAC 2017)

Abstract
We consider the problem of packing a family of disks 'on a shelf,' that is, such that each disk touches the x-axis from above and such that no two disks overlap. We prove that the problem of minimizing the distance between the leftmost point and the rightmost point of any disk is NP-hard. On the positive side, we show how to approximate this problem within a factor of 4/3 in O(n log n) time, and provide an O(n log n)-time exact algorithm for a special case, in particular when the ratio between the largest and smallest radius is at most four.
Cite as

Helmut Alt, Kevin Buchin, Steven Chaplick, Otfried Cheong, Philipp Kindermann, Christian Knauer, and Fabian Stehn. Placing your Coins on a Shelf. In 28th International Symposium on Algorithms and Computation (ISAAC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 92, pp. 4:1-4:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{alt_et_al:LIPIcs.ISAAC.2017.4,
  author =	{Alt, Helmut and Buchin, Kevin and Chaplick, Steven and Cheong, Otfried and Kindermann, Philipp and Knauer, Christian and Stehn, Fabian},
  title =	{{Placing your Coins on a Shelf}},
  booktitle =	{28th International Symposium on Algorithms and Computation (ISAAC 2017)},
  pages =	{4:1--4:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-054-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{92},
  editor =	{Okamoto, Yoshio and Tokuyama, Takeshi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2017.4},
  URN =		{urn:nbn:de:0030-drops-82145},
  doi =		{10.4230/LIPIcs.ISAAC.2017.4},
  annote =	{Keywords: packing problems, approximation algorithms, NP-hardness}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2016.11
Approximating Smallest Containers for Packing Three-Dimensional Convex Objects

Authors: Helmut Alt and Nadja Scharf

Published in: LIPIcs, Volume 64, 27th International Symposium on Algorithms and Computation (ISAAC 2016)

Abstract
We investigate the problem of computing a minimum-volume container for the non-overlapping packing of a given set of three-dimensional convex objects. Already the simplest versions of the problem are NP-hard so that we cannot expect to find exact polynomial time algorithms. We give constant ratio approximation algorithms for packing axis-parallel (rectangular) cuboids under translation into an axis-parallel (rectangular) cuboid as container, for packing cuboids under rigid motions into an axis-parallel cuboid or into an arbitrary convex container, and for packing convex polyhedra under rigid motions into an axis-parallel cuboid or arbitrary convex container. This work gives the first approximability results for the computation of minimum volume containers for the objects described.
Cite as

Helmut Alt and Nadja Scharf. Approximating Smallest Containers for Packing Three-Dimensional Convex Objects. In 27th International Symposium on Algorithms and Computation (ISAAC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 64, pp. 11:1-11:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{alt_et_al:LIPIcs.ISAAC.2016.11,
  author =	{Alt, Helmut and Scharf, Nadja},
  title =	{{Approximating Smallest Containers for Packing Three-Dimensional Convex Objects}},
  booktitle =	{27th International Symposium on Algorithms and Computation (ISAAC 2016)},
  pages =	{11:1--11:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-026-2},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{64},
  editor =	{Hong, Seok-Hee},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2016.11},
  URN =		{urn:nbn:de:0030-drops-67801},
  doi =		{10.4230/LIPIcs.ISAAC.2016.11},
  annote =	{Keywords: computational geometry, packing, approximation algorithm}
}
Document
DOI: 10.4230/DagSemProc.09111.1
09111 Abstracts Collection – Computational Geometry

Authors: Pankaj Kumar Agarwal, Helmut Alt, and Monique Teillaud

Published in: Dagstuhl Seminar Proceedings, Volume 9111, Computational Geometry (2009)

Abstract
From March 8 to March 13, 2009, the Dagstuhl Seminar 09111 ``Computational Geometry '' was held in Schloss Dagstuhl~--~Leibniz Center for Informatics. During the seminar, several participants presented their current research, and ongoing work and open problems were discussed. Abstracts of the presentations given during the seminar as well as abstracts of seminar results and ideas are put together in this paper. The first section describes the seminar topics and goals in general. Links to extended abstracts or full papers are provided, if available.
Cite as

Pankaj Kumar Agarwal, Helmut Alt, and Monique Teillaud. 09111 Abstracts Collection – Computational Geometry. In Computational Geometry. Dagstuhl Seminar Proceedings, Volume 9111, pp. 1-18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{agarwal_et_al:DagSemProc.09111.1,
  author =	{Agarwal, Pankaj Kumar and Alt, Helmut and Teillaud, Monique},
  title =	{{09111 Abstracts Collection – Computational Geometry}},
  booktitle =	{Computational Geometry},
  pages =	{1--18},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2009},
  volume =	{9111},
  editor =	{Pankaj Kumar Agarwal and Helmut Alt and Monique Teillaud},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.09111.1},
  URN =		{urn:nbn:de:0030-drops-20346},
  doi =		{10.4230/DagSemProc.09111.1},
  annote =	{Keywords: }
}
Document
DOI: 10.4230/DagSemRep.109
Computational Geometry (Dagstuhl Seminar 9511)

Authors: Helmut Alt, Bernard Chazelle, and Raimund Seidel

Published in: Dagstuhl Seminar Reports. Dagstuhl Seminar Reports, Volume 1 (2021)

Abstract
Cite as

Helmut Alt, Bernard Chazelle, and Raimund Seidel. Computational Geometry (Dagstuhl Seminar 9511). Dagstuhl Seminar Report 109, pp. 1-27, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (1995)

Copy BibTex To Clipboard

@TechReport{alt_et_al:DagSemRep.109,
  author =	{Alt, Helmut and Chazelle, Bernard and Seidel, Raimund},
  title =	{{Computational Geometry (Dagstuhl Seminar 9511)}},
  pages =	{1--27},
  ISSN =	{1619-0203},
  year =	{1995},
  type = 	{Dagstuhl Seminar Report},
  number =	{109},
  institution =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemRep.109},
  URN =		{urn:nbn:de:0030-drops-149970},
  doi =		{10.4230/DagSemRep.109},
}
Document
DOI: 10.4230/DagSemRep.59
Computational Geometry (Dagstuhl Seminar 9312)

Authors: Helmut Alt, Bernard Chazelle, and Emo Welzl

Published in: Dagstuhl Seminar Reports. Dagstuhl Seminar Reports, Volume 1 (2021)

Abstract
Cite as

Helmut Alt, Bernard Chazelle, and Emo Welzl. Computational Geometry (Dagstuhl Seminar 9312). Dagstuhl Seminar Report 59, pp. 1-28, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (1993)

Copy BibTex To Clipboard

@TechReport{alt_et_al:DagSemRep.59,
  author =	{Alt, Helmut and Chazelle, Bernard and Welzl, Emo},
  title =	{{Computational Geometry (Dagstuhl Seminar 9312)}},
  pages =	{1--28},
  ISSN =	{1619-0203},
  year =	{1993},
  type = 	{Dagstuhl Seminar Report},
  number =	{59},
  institution =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemRep.59},
  URN =		{urn:nbn:de:0030-drops-149479},
  doi =		{10.4230/DagSemRep.59},
}
Document
DOI: 10.4230/DagSemRep.22
Computational Geometry (Dagstuhl Seminar 9141)

Authors: Helmut Alt, Bernard Chazelle, and Emo Welzl

Published in: Dagstuhl Seminar Reports. Dagstuhl Seminar Reports, Volume 1 (2021)

Abstract
Cite as

Helmut Alt, Bernard Chazelle, and Emo Welzl. Computational Geometry (Dagstuhl Seminar 9141). Dagstuhl Seminar Report 22, pp. 1-27, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (1991)

Copy BibTex To Clipboard

@TechReport{alt_et_al:DagSemRep.22,
  author =	{Alt, Helmut and Chazelle, Bernard and Welzl, Emo},
  title =	{{Computational Geometry (Dagstuhl Seminar 9141)}},
  pages =	{1--27},
  ISSN =	{1619-0203},
  year =	{1991},
  type = 	{Dagstuhl Seminar Report},
  number =	{22},
  institution =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemRep.22},
  URN =		{urn:nbn:de:0030-drops-149101},
  doi =		{10.4230/DagSemRep.22},
}

Helmut, Alt

Document
DOI: 10.4230/DagSemRep.4
Algorithmic Geometry (Dagstuhl Seminar 9041)

Authors: Alt Helmut and Welzl Emo

Published in: Dagstuhl Seminar Reports. Dagstuhl Seminar Reports, Volume 1 (2021)

Abstract
Cite as

Alt Helmut and Welzl Emo. Algorithmic Geometry (Dagstuhl Seminar 9041). Dagstuhl Seminar Report 4, pp. 1-19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (1991)

Copy BibTex To Clipboard

@TechReport{helmut_et_al:DagSemRep.4,
  author =	{Helmut, Alt and Emo, Welzl},
  title =	{{Algorithmic Geometry (Dagstuhl Seminar 9041)}},
  pages =	{1--19},
  ISSN =	{1619-0203},
  year =	{1991},
  type = 	{Dagstuhl Seminar Report},
  number =	{4},
  institution =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemRep.4},
  URN =		{urn:nbn:de:0030-drops-148928},
  doi =		{10.4230/DagSemRep.4},
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact